/**
 * Segment Tree (线段树) 实现
 * 
 * 线段树是一种二叉树数据结构，用于处理区间查询和区间更新问题。
 * 它可以在O(log n)时间内完成区间查询和区间更新操作。
 * 
 * 时间复杂度：
 * - 构建: O(n)
 * - 区间查询: O(log n)
 * - 区间更新: O(log n)
 * - 单点更新: O(log n)
 * 
 * 空间复杂度: O(4n)
 */

class SegmentTree {
  constructor(arr) {
    // TODO: 初始化线段树
    // this.n = arr.length
    // this.tree = new Array(4 * this.n)
    // this.lazy = new Array(4 * this.n).fill(0)
    // this.build(arr, 0, 0, this.n - 1)
  }

  /**
   * 构建线段树
   * @param {number[]} arr - 原始数组
   * @param {number} node - 当前节点索引
   * @param {number} start - 区间开始
   * @param {number} end - 区间结束
   */
  build(arr, node, start, end) {
    // TODO: 实现线段树构建逻辑
    // 1. 如果是叶子节点，直接赋值
    // 2. 否则递归构建左右子树
    // 3. 当前节点值为左右子树值的和
  }

  /**
   * 区间查询
   * @param {number} node - 当前节点索引
   * @param {number} start - 当前区间开始
   * @param {number} end - 当前区间结束
   * @param {number} l - 查询区间开始
   * @param {number} r - 查询区间结束
   * @returns {number} - 区间和
   */
  queryRange(node, start, end, l, r) {
    // TODO: 实现区间查询逻辑
    // 1. 处理懒加载标记
    // 2. 如果查询区间与当前区间不重叠，返回0
    // 3. 如果查询区间完全包含当前区间，返回当前节点值
    // 4. 否则递归查询左右子树
  }

  /**
   * 区间更新
   * @param {number} node - 当前节点索引
   * @param {number} start - 当前区间开始
   * @param {number} end - 当前区间结束
   * @param {number} l - 更新区间开始
   * @param {number} r - 更新区间结束
   * @param {number} val - 更新值
   */
  updateRange(node, start, end, l, r, val) {
    // TODO: 实现区间更新逻辑
    // 1. 处理懒加载标记
    // 2. 如果更新区间与当前区间不重叠，直接返回
    // 3. 如果更新区间完全包含当前区间，更新当前节点并设置懒加载标记
    // 4. 否则递归更新左右子树
  }

  /**
   * 单点更新
   * @param {number} node - 当前节点索引
   * @param {number} start - 当前区间开始
   * @param {number} end - 当前区间结束
   * @param {number} idx - 更新位置
   * @param {number} val - 更新值
   */
  updatePoint(node, start, end, idx, val) {
    // TODO: 实现单点更新逻辑
    // 1. 如果是叶子节点，直接更新
    // 2. 否则根据位置递归更新左子树或右子树
    // 3. 更新当前节点值
  }

  /**
   * 单点查询
   * @param {number} node - 当前节点索引
   * @param {number} start - 当前区间开始
   * @param {number} end - 当前区间结束
   * @param {number} idx - 查询位置
   * @returns {number} - 查询值
   */
  queryPoint(node, start, end, idx) {
    // TODO: 实现单点查询逻辑
    // 1. 如果是叶子节点，返回当前值
    // 2. 否则根据位置递归查询左子树或右子树
  }

  /**
   * 获取区间和
   * @param {number} l - 区间开始
   * @param {number} r - 区间结束
   * @returns {number} - 区间和
   */
  getRangeSum(l, r) {
    // TODO: 调用queryRange方法
  }

  /**
   * 区间更新值
   * @param {number} l - 区间开始
   * @param {number} r - 区间结束
   * @param {number} val - 更新值
   */
  updateRangeValue(l, r, val) {
    // TODO: 调用updateRange方法
  }

  /**
   * 单点更新值
   * @param {number} idx - 位置
   * @param {number} val - 更新值
   */
  updateSingleValue(idx, val) {
    // TODO: 调用updatePoint方法
  }

  /**
   * 获取单点值
   * @param {number} idx - 位置
   * @returns {number} - 值
   */
  getSingleValue(idx) {
    // TODO: 调用queryPoint方法
  }
}

module.exports = SegmentTree